Recent rapid development of Online Social Networks (OSNs) has revolutionized the way of human interaction and drastically changed the landscape of communications and information sharing. One of the most important characteristics of OSNs is the “word-of-mouth” exchanges, in which information can be propagated from friends to friends of friends and eventually widely spread over the network. By leveraging this power, many organizations and companies have been using OSNs as an effective medium to increase their visibility and advertise their products. Likewise, millions of OSN users are sharing their personal status daily with a hope to keep many of their friends, near or far, updated. However, millions of users are tweeting and sharing their personal status daily without being aware of where that information eventually travels to.
Indeed, not only is it possible to quickly propagate information to friends, this information may be spread to many unwanted targets (those with whom we do not want to share the information). For example, suppose that Bob wants to share with his friends some of his personal pictures and stories in Facebook, yet he is reluctant to let Chuck know about them. Being careful, Bob just shares to the list of his friends in Facebook where Chuck is not in that group with a belief that Chuck cannot see those pictures. Unfortunately, Alice, who is a friend of both Bob and Chuck, replied to the post, and thus Chuck will be able to see the message from Alice and learn about Bob's sharing.
Current OSN settings can address part of this issue. For example, Google+ groups users into circles such that a user can select a specific circle to share information with when the user shares a message. In addition, Facebook includes a function enabling customized privacy for each user when the user shares a message (referred to as “Custom Privacy”). In the Custom Privacy function, a user can choose a range of friends to share with and also hide the message from some specific users (including friends, friends of friends, or the public). Superficially, the information leakage problem appears to be addressed in the OSNs by these user-selected privacy controls. In particular, the Custom Privacy function works by tracking the message-ID associated with a post and hiding any post or thread having that message-ID from unwanted targets. However, the current approaches neglect an important channel of information propagation, namely, mentioning the message.
In the example with Bob and Chuck, Bob may use the custom privacy function provided by Facebook to hide his sharing from Chuck, which can help avoid the situation where Chuck see's Alice's reply to the post (and thus the pictures or post shared by Bob). Unfortunately, the custom privacy function only tracks and hides Alice's message based on the message-ID of Bob's post, not on its propagation. Therefore, when Bob's friend Alice posts a new message mentioning Bob's pictures and stories, this new message cannot be hidden from Chuck anymore since its ID is no longer the same as the original message from Bob. Consequently, Chuck will still learn about Bob's pictures and stories. Thus it raises a practical question: Is there any mechanism for Bob to share his pictures and stories to as many friends as possible without these pictures and stories reaching Chuck?